#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 随机访问数组元素  时间复杂度O(1)
int rondomAccess(int *arr, int size)
{
    srand(time(NULL));
    return arr[rand() % size];
}

// 顺序访问数组元素  时间复杂度O(n)
void sequentialAccess(int *arr, int size)
{
    for (int i = 0; i < size; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 插入  时间复杂度O(n)
void insert(int *arr, int *size, int capacity, int index, int value)
{
    // printf("insert!\n");
    if (*size >= capacity)
    {
        printf("插入位置%d,插入数值%d失败!数组已满!!!\n", index, value);
        return;
    }
    for (int i = *size; i > index; i--)
    {
        arr[i] = arr[i - 1];
    }
    arr[index] = value;
    *size += 1;
}

// 删除  时间复杂度O(n)
int delete(int *arr, int *size, int index)
{
    printf("delete!\n");
    if (index >= *size)
    {
        return -1;
    }
    for (int i = index; i < *size - 1; i++)
    {
        arr[i] = arr[i + 1];
    }
    return --(*size);
}

// 查找  时间复杂度O(n)
int find(int *arr, int size, int value)
{
    for (int i = 0; i < size; i++)
    {
        if (arr[i] == value)
        {
            return i;
        }
    }
    return -1;
}

// 数组扩容 每次容量翻倍
int *expand(int *arr, int *capacity)
{
    printf("expand!\n");
    int *temp = (int *)malloc(sizeof(int) * (*capacity) * 2);
    for (int i = 0; i < 2 * (*capacity); i++)
    {
        if (i < *capacity)
        {
            temp[i] = arr[i];
        }
        else
        {
            temp[i] = 0;
        }
    }
    *capacity = *capacity * 2;
    // arr = temp;
    printf("扩容后数组容量:%d\n", *capacity);
    printf("temp:%d\n", sizeof(temp));
    return temp;
}

int main()
{
    // 数组初始化   数组的容量  数组的有效元素个数
    int arr[10] = {1, 2, 3, 4, 5};
    int size = 5;
    int capacity = sizeof(arr) / sizeof(int);
    // 访问数组元素 arr == &arr[0]
    // int *p = arr;
    // printf("%d\n", *(p + 0));
    // printf("%d\n", arr[0]);

    // printf("%d\n", rondomAccess(arr, 5));
    insert(arr, &size, capacity, 0, 100);
    insert(arr, &size, capacity, 0, 90);
    insert(arr, &size, capacity, 0, 80);
    insert(arr, &size, capacity, 0, 70);
    insert(arr, &size, capacity, 0, 60);
    insert(arr, &size, capacity, 0, 50);
    sequentialAccess(arr, size);

    delete(arr, &size, 2);
    sequentialAccess(arr, size);

    printf("find 100: %d\n", find(arr, size, 100));

    int *newArr = expand(arr, &capacity);

    sequentialAccess(newArr, size);
    printf("capacity:%d\n", capacity);
    free(newArr);
    return 0;
}